package org.example.Soution001;

import java.util.*;

public class KthSmallest {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(32);
        root.left = new TreeNode(26);
        root.right = new TreeNode(47);
        root.left.left = new TreeNode(19);
        root.left.right = new TreeNode(30);
        root.right.right = new TreeNode(56);
        KthSmallest kthSmallest = new KthSmallest();
        System.out.println(kthSmallest.kthSmallest(root, 2));

    }

    public int kthSmallest(TreeNode root, int k) {
        MyBST myBST=new MyBST(root);
        System.out.println(myBST.map.get(root)+" "+myBST.map.get(root.left)+" "+myBST.map.get(root.right));
        return myBST.kthSmallest(k);
    }

//    int count=0;
//    public int kthSmallest(TreeNode root, int k) {
//        return inorderTraversal(root,k).val;
//    }
//
//    public TreeNode inorderTraversal(TreeNode root, int k) {
//        if(root == null) return null;
//        TreeNode left = inorderTraversal(root.left,k);
//        if(left!=null) return left;
//        if(count == k-1){
//            return root;
//        }
//        count++;
//        TreeNode right = inorderTraversal(root.right,k);
//        if(right!=null) return right;
//        return null;
//    }

//    Deque<TreeNode> stack=new ArrayDeque<>();
//    public int kthSmallest(TreeNode root, int k) {
//        //中序遍历 用栈
//        while(root!=null||!stack.isEmpty()){
//            while(root!=null){
//                stack.push(root);
//                root=root.left;
//            }
//            root=stack.pop();
//            k--;
//            if(k==0){
//                break;
//            }
//            root=root.right;
//        }
//        return root.val;
//    }
}

class MyBST {
    TreeNode root;
    Map<TreeNode, Integer> map;

    public MyBST(TreeNode root) {
        this.root = root;
        this.map = new HashMap<TreeNode, Integer>();
        countNodeNum(root);
    }


    public int kthSmallest(int k) {
        TreeNode node = root;
        while(node!=null) {
            int left=map.getOrDefault(node.left,0);
            if(left<k-1){
                node = node.right;
                k-=left+1;
            }else if(left==k-1){
                break;
            }else{
                node = node.left;
            }
        }
        return node.val;
    }

    public int countNodeNum(TreeNode root) {
        if(root == null) return 0;
        map.put(root,1+countNodeNum(root.left)+countNodeNum(root.right));
        return map.get(root);
    }
}
